import java.util.Arrays;

public class Main {
    //调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
//如数组：[1,2,3,4,5,6]
//调整后可能是：[1, 5, 3, 4, 2, 6]
    public static void main7(String[] args) {
        int[] a = {1,2,3,4,5,6,4,6,5,6,8};
        int left = 0;
        int right = a.length-1;
        while( left < right) {
            while( left < right  && a[left] % 2 != 0) {
                left++;
            }
            while(left < right &&a[right] % 2 == 0) {
                right--;
            }
            int temp = a[right];
            a[right--] = a[left];
            a[left++] = temp;

        }
        System.out.println(Arrays.toString(a));
    }


    //给定一个有序整型数组, 实现二分查找
    public static int search(int[] a, int left, int right, int goal) {
        while(left <= right) {
            int num = (right+left) / 2;
            if(a[num] < goal) {
                left = num + 1;
            }else if(a[num] > goal) {
                right = num - 1;
            }else{
                return num;
            }
        }
        return -1;
    }
    public static void main1(String[] args) {
        int[] a = {1,2,3,4,4,5,6,7,8,9,10,11};
        System.out.println(Arrays.binarySearch(a,4));
        System.out.println(search(a, 0, a.length-1, 4));
    }

    //给定一个整型数组, 实现冒泡排序(升序排序)
    public static void main2(String[] args) {
        int[] a = {1,4,7,2,5,8,3,6,9,1,10};
        for (int i = 0; i < a.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < a.length-1-i; j++) {
                if(a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = true;
                }
            }
            if(flag == false) {
                break;
            }
        }
        System.out.println(Arrays.toString(a));
    }

    //给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
//你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
//你可以按任意顺序返回答
//示例 1：
//输入：nums = [2,7,11,15], target = 9
//输出：[0,1]
//解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
    public static void main3(String[] args) {
        int[] nums = {2,7,11,15,9,0,4,5};
        int target = 9;
        int k = 0;
        int[] a = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    a[k] = i;
                    a[k+1] = j;
                    k += 2;
                }
            }
        }
        for (int i = 0; i < k; i++) {
            System.out.print(a[i] + " ");

        }
    }

    //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//示例 1
//输入: [2,2,1]
//输出: 1
//示例 2:
//输入: [4,1,2,1,2]
//输出: 4
    public static void main4(String[] args) {
        int[] a = {2,2,1,4,4};
//    Arrays.sort(a);
//    if(a[0] != a[1]) {
//        System.out.println(a[0]);
//    }
//    for (int i = 1; i < a.length-1; i++) {
//        if(a[i] != a[i+1] && a[i] != a[i-1]) {
//            System.out.println(a[i]);
//        }
//    }
        int ret = a[0];
        for (int i = 1; i < a.length; i++) {
            ret ^= a[i];
        }
        System.out.println(ret);
    }
    //给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：[3,2,3]
//输出：3
//示例 2：
//输入：[2,2,1,1,1,2,2]
//输出：2
    public static void main5(String[] args) {
        int[] a = {3,2,3,4,5,4,4,4,4};
//    for(int i = 0; i < a.length; i++) {
//        int flag = 0;
//        for(int j = 0; j < a.length; j++) {
//            if(a[i] == a[j]) {
//                flag++;
//            }
//        }
//        if(flag > (a.length / 2)){
//            System.out.println(a[i]);
//            break;
//        }
//    }
        Arrays.sort(a);
        System.out.println(a[a.length/2]);

    }

    //给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
//示例 1：
//输入：arr = [2,6,4,1]
//输出：false
//解释：不存在连续三个元素都是奇数的情况。
//示例 2：
//输入：arr = [1,2,34,3,4,5,7,23,12]
//输出：true
//解释：存在连续三个元素都是奇数的情况，即 [5,7,23]
    public static void main6(String[] args) {
        int[] arr = {1,2,34,3,4,5,7,23,12};
        boolean flag = false;
        for (int i = 0; i < arr.length-2; i++) {
            if(arr[i] % 2 != 0 && arr[i+1] % 2 != 0 && arr[i+2] % 2 !=0){
                flag = true;
            }
        }
        System.out.println(flag);
    }
}